class Solution
{
public:
    int rootCount(vector<vector<int>> &edges, vector<vector<int>> &guesses, int k)
    {
        int n = edges.size() + 1;
        vector<vector<long long>> graph(n);
        for (auto &edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        int shift = 17;
        unordered_set<long long> guessSet;
        for (auto &guess : guesses)
        {
            long long a = guess[0];
            long long b = guess[1];
            guessSet.insert((a << shift) + b);
        }

        int rightGuess = 0;
        function<void(long long, long long)> dfs = [&](long long node, long long parent)
        {
            for (long long neighbor : graph[node])
            {
                if (neighbor == parent)
                {
                    continue;
                }
                if (guessSet.count((node << shift) + neighbor))
                {
                    ++rightGuess;
                }
                dfs(neighbor, node);
            }
        };
        dfs(0, -1);

        int result = 0;
        function<void(long long, long long, int)> dfsDp = [&](long long node, long long parent, int parentRightGuess)
        {
            int nodeRightGuess = parentRightGuess;
            if (parent != -1)
            {
                long long uv = (parent << shift) + node;
                long long vu = (node << shift) + parent;
                if (guessSet.count(uv))
                {
                    --nodeRightGuess;
                }
                if (guessSet.count(vu))
                {
                    ++nodeRightGuess;
                }
            }
            if (nodeRightGuess >= k)
            {
                ++result;
            }
            for (long long neighbor : graph[node])
            {
                if (neighbor == parent)
                {
                    continue;
                }
                dfsDp(neighbor, node, nodeRightGuess);
            }
        };
        dfsDp(0, -1, rightGuess);

        return result;
    }
};